package cn.cxq.learning.string_matching;

import org.junit.jupiter.api.Test;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/02e7cc263f8a49e8b1e1dc9c116f7602?toCommentId=9172238
 * 来源：牛客网
 *
 * [编程题]最长公共子串
 * 热度指数：11968时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
 * 算法知识视频讲解
 * 对于两个字符串，请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度)，求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,...Vn，其中Ui + 1 == Ui+1,Vi + 1 == Vi+1，同时Ui == Vi。
 *
 * 给定两个字符串A和B，同时给定两串的长度n和m。
 *
 * 测试样例：
 * "1AB2345CD",9,"12345EF",7
 * 返回：4
 */
public class FindLongest {

    @Test
    public void test() {
        System.out.println(findLongest("1AB2345CD", 9, "12345EF", 7));
    }

//    public int findLongest(String A, int n, String B, int m) {
//        if(A == null || A.length() == 0 || B == null || B.length() == 0){
//            return -1;
//        }
//        int lengthA = n + 1;
//        int lengthB = m + 1;
//        char[] arrayA = A.toCharArray();
//        char[] arrayB = B.toCharArray();
//        int[][] stateArray = new int[lengthA][lengthB];
//        int maxLength = 0;
//        for(int i = 0;i < n;i++ ){
//            for(int j = 0;j < m;j++){
//                if(arrayA[i] == arrayB[j]){
//                    stateArray[i+1][j+1]=stateArray[i][j]+1;
//                    if(stateArray[i+1][j+1] > maxLength){
//                        maxLength = stateArray[i+1][j+1];
//                    }
//                }
//            }
//        }
//        return maxLength;
//    }

    // 动态规划解决最长公共子串问题：
    public int findLongest(String A, int n, String B, int m) {

        if (A.length() == 0 || n == 0 || B.length() == 0 || m == 0) {
            return 0;
        }

        int[][] dp = new int[A.length() + 1][B.length() + 1];

        int maxLength = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (A.charAt(i) == B.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                    if (maxLength < dp[i + 1][j + 1]) {
                        maxLength = dp[i + 1][j + 1];
                    }
                }
            }
        }

        return maxLength;
    }

}